/**
 * 斐波那契数列（Fibonacci sequence）
 *
 * 斐波那契数（Fibonacci number）
 * ---------------------------------
 * 文档查看: /document/algo/fibonacci_sequence.md
 * 2021-01-18
 *
 * --------------------
 * VSCode 中运行 C语言
 * 1. 右键运行`run code`
 * 2. 选中可执行文件 右键 open xxx terminal
 * 3. ./xxxx(可执行文件) 回车运行
 *    TERMINAL: .fibonacci_sequence 回车
 * 4. 在 OUTPUT: 右键 `Stop code run`
 *
 * --------------------
 * 【C语言】斐波那契数列四种优化求解
 * https://blog.csdn.net/qq_41035588/article/details/81814547
 */

#include <stdio.h>

// 时间复杂度O(N)
// 空间复杂度O(1)
long long fib(long n) {
  if (n < 2) return n;
  long i, numPre = 0, numNext = 1;
  for (int i = 2; i <= n; i++) {
    long sum = numPre + numNext;
    numPre = numNext;
    numNext = sum;
  }
  return numNext;
}

int main() {
  // 退出按键 == 0
  int n = 0;
  printf("输出数列第几项的值：");
  for(;scanf("%d", &n);) {
    long long result = fib(n);
    printf("\nn=%d, result=%lld\n", n, result);
    if (n == 0) {
      break;
    }
    printf("\n 输出数列第几项的值：");
  }
}


